1. Description of the Related Art
A cache device typically has a larger storage capacity than the backing store with which the cache device is associated. As a cache device fills with cached data, certain cached data may be evicted to free up room to cache additional data. If data is evicted from a cache device, a subsequent request for the evicted data yields a cache miss. Evicting the wrong data from a cache device can increase the number of cache misses and decrease the efficiency of the cache device.
2. Brief Summary
From the foregoing discussion, it should be apparent that a need exists for an apparatus, system, and method that optimally manage eviction of data from a cache. Beneficially, such an apparatus, system, and method would selectively evict data of a cache based on a grooming cost.
The present invention has been developed in response to the present state of the art, and in particular, in response to the problems and needs in the art that have not yet been fully solved by currently available data caches. Accordingly, the present invention has been developed to provide an apparatus, system, and method for managing eviction of data that overcome many or all of the above-discussed shortcomings in the art.
A method of the present invention is presented for managing eviction of data. In one embodiment, the method includes examining a grooming cost for a selected region of a nonvolatile solid-state cache. The method, in another embodiment, includes adding the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold. The grooming candidate set, in one embodiment, includes a plurality of regions of the nonvolatile solid-state cache ordered by grooming cost. In a further embodiment, the method includes selecting a low cost region within the grooming candidate set. The low cost region, in one embodiment, has a lowest grooming cost of members of the grooming candidate set.
The grooming cost, in one embodiment, includes a cost of evicting a selected region of the nonvolatile solid-state cache relative to other regions. In a further embodiment, the grooming cost represents a cache efficiency cost of evicting data from a selected region and a storage efficiency cost of copying data forward from a selected region. The grooming cost for a selected region, in another embodiment, accounts for an amount of cached dirty write data of a selected region. The grooming cost of a selected region, in one embodiment, satisfies the grooming cost threshold by being lower than at least one region of the grooming candidate set.
In one embodiment, the method includes recovering storage capacity of the low cost region. The method, in a further embodiment, includes retaining cached dirty write data from the low cost region in response to recovering the storage capacity of the low cost region. In another embodiment, the method includes retaining cached data identified as frequently accessed data from the low cost region in response to recovering the storage capacity of the low cost region in a low pressure groom mode. The method, in one embodiment, includes evicting cached data identified as frequently accessed data in response to recovering the storage capacity of the low cost region in a high pressure groom mode. Recovering the storage capacity of the low cost region, in one embodiment, is in response to a storage capacity recovery event. In a further embodiment, recovering the storage capacity of the low cost region is in response to a grooming pressure for the nonvolatile solid-state cache exceeding a predefined grooming pressure threshold.
In one embodiment, the method includes selecting a next region of the nonvolatile solid-state cache as a selected region in response to the grooming cost of the previous selected region failing to satisfy the grooming cost threshold. In a further embodiment, regions of the nonvolatile solid-state cache are organized in a circular data structure. In another embodiment, the method includes selecting one or more successive next regions in order around the circular data structure until a grooming cost for a next region satisfies the grooming cost threshold and the next region that satisfies the grooming cost threshold is added to the grooming candidate set.
In one embodiment, the grooming cost for a selected region is based at least partially on a frequency count for a selected region. The method, in one embodiment, includes clearing the frequency count for a selected region in response to examining the grooming cost for a selected region such that a subsequent grooming cost for the selected region is based at least partially on a new frequency count for the selected region. In a further embodiment, the method includes preserving a copy of the frequency count for a selected region in response to adding the selected region to the grooming candidate set. The frequency count, in one embodiment, identifies frequently accessed data from a low cost region. In a further embodiment, the frequency count comprises a number or an amount of blocks in a selected region accessed at least a predetermined number of times during a predefined time period.
In one embodiment, the selected region stores data for a plurality of cache units. The grooming cost, in certain embodiments, accounts for one or more attributes of the plurality of cache units. The one or more attributes may include a relative priority of the cache units, an allocated storage capacity for the cache units, a quality-of-service for the cache units, or the like.
An apparatus to manage eviction of data is provided with a plurality of modules configured to functionally execute the necessary steps of managing eviction of data from a cache. These modules in the described embodiments include a grooming cost module, a grooming candidate set module, a low cost module, a groomer module, a grooming clock module, and a frequency count module.
In one embodiment, the grooming cost module determines a grooming cost for a selected region of a nonvolatile solid-state cache. The grooming cost, in certain embodiments, includes a cost of evicting the selected region of the nonvolatile solid-state cache relative to other regions. In a further embodiment, the grooming candidate set module adds a selected region to a grooming candidate set in response to the grooming cost of the selected region satisfying a grooming cost threshold. The grooming cost of a selected region, in another embodiment, satisfies the grooming cost threshold by being lower than at least one region of the grooming candidate set.
In one embodiment, the low cost module selects a low cost region within the grooming candidate set. The low cost region, in another embodiment, has a lowest grooming cost of members of the grooming candidate set. In one embodiment, the groomer module recovers storage capacity of the low cost region. The groomer module, in a further embodiment, retains cached dirty write data from the low cost region. In another embodiment, the groomer module retains cached data identified as frequently accessed data from the low cost region in response to recovering the storage capacity of the low cost region in a low pressure groom mode. The groomer module, in an additional embodiment, evicts cached data identified as frequently accessed data in response to recovering the storage capacity of the low cost region in a high pressure groom mode.
In one embodiment, the grooming clock module selects the selected region. In a further embodiment, the grooming clock module selects a next region of the nonvolatile solid-state cache as the selected region in response to the grooming cost of the selected region failing to satisfy the grooming cost threshold.
In one embodiment, the frequency count module determines a frequency count for the selected region. The grooming cost module, in a further embodiment, bases the grooming cost for the selected region at least partially on the frequency count.
A system of the present invention is also presented to manage eviction of data. The system may be embodied by a processor, a storage controller, and a cache controller. In particular, the system, in one embodiment, includes a host computer system.
The storage controller, in one embodiment, is for a nonvolatile solid-state storage device. The nonvolatile solid-state storage device, in a further embodiment, is in communication with the processor over one or more communications buses. The cache controller, in another embodiment, is in communication with the storage controller.
The cache controller, in one embodiment, includes a grooming cost module. The grooming cost module, in a further embodiment, is in communication with the storage controller. In another embodiment, the grooming cost module examines a grooming cost for a selected region of the nonvolatile solid-state storage device. The grooming cost, in one embodiment, includes a cost of evicting the selected region of the nonvolatile solid-state storage device relative to other regions.
In a further embodiment, the cache controller includes a grooming candidate set module. The grooming candidate set module, in one embodiment, adds the selected region to a grooming candidate set in response to the grooming cost satisfying a grooming cost threshold. In another embodiment, the cache controller includes a low cost module that selects a low cost region within the grooming candidate set. The cache controller, in a further embodiment, includes a groomer module that recovers storage capacity of the low cost region. In one embodiment, the groomer module is in communication with the storage controller.
References throughout this specification to features, advantages, or similar language do not imply that all of the features and advantages may be realized in any single embodiment. Rather, language referring to the features and advantages is understood to mean that a specific feature, advantage, or characteristic is included in at least one embodiment. Thus, discussion of the features and advantages, and similar language, throughout this specification may, but do not necessarily, refer to the same embodiment.
Furthermore, the described features, advantages, and characteristics of the embodiments may be combined in any suitable manner. One skilled in the relevant art will recognize that the embodiments may be practiced without one or more of the specific features or advantages of a particular embodiment. In other instances, additional features and advantages may be recognized in certain embodiments that may not be present in all embodiments.
These features and advantages of the embodiments will become more fully apparent from the following description and appended claims, or may be learned by the practice of embodiments as set forth hereinafter.